/*
好久前的一次沙龙课的时候，
学生给了道赴微软面试的题目，
临时写了这个程序，
可能算法不是最好的，
但我感觉足以应付你的面试了。
今天拿出来和大家分享，
希望能有助于大家找到好的工作。

Fun(int a[n], int sum),
其功能是找出数组a[n]中所有两个数之和等于sum的组合情况。

#include<stdio.h>
#define Max 5
void Fun(int a[Max],int sum)
{
	int i,j;
	for(i=0;i<Max-1;i++)
		for(j=i+1;j<Max;j++)
			if(a[i]+a[j]==sum)
				printf("a[%d]和a[%d]的和等于sum,其和为%d",i,j,sum);
}

void main()
{
	int b[Max],k=2,i;
	printf("请输入数组b的值\n");
	for(i=0;i<Max;i++)
		scanf("%d",&b[i]);
	Fun(b,k);
}

*/
#include "junix.h"

void Fun(int v[], int size, int sum) {
	typedef std::vector<std::list<int> > hashtable;
	hashtable ht(sum,std::list<int>());

	for (int i=0;i<size;i++)
		ht[v[i]%sum].push_back(v[i]);

	for (int i=0;i<sum;i++) 
		ht[i].sort();

	for (int i=0;i<sum/2;i++) {
		int other = (sum-i)%sum;
		typedef std::list<int>::iterator iterator;
		iterator apos=ht[i].begin(), 
				 bpos=--ht[other].end();

		while (apos!= ht[i].end() && bpos!=ht[other].end()) {
			int tsum = *apos + *bpos;
			if (tsum == sum) {
				int asz=1,bsz=1;
				int av=*apos++,bv=*bpos--;
				while (apos!=ht[i].end() && *apos== av) { 
					++apos;
					++asz; 
				}
				
				while (bpos!=ht[other].end() &&*bpos == bv){
					--bpos;
				   	++bsz;
			   	}

				for (int i=0;i<asz*bsz;i++)
					printf("a=%d,b=%d\n",av, bv);
			} else if (tsum < sum) {
				++ apos;
			} else {
				--bpos;
			}
		}
	}
}

int main(){
	int v[]={1,2,3,3,3,4,5,6,6,7,8,9,10};
	Fun(v,sizeof(v)/sizeof(v[0]),9);
}
